% !TEX TS-program = pdflatex
\documentclass[10pt, a4paper]{article}

\usepackage{a4wide}
\usepackage{color}
\usepackage{amsmath,amssymb,epsfig,pstricks,xspace}
\usepackage{german,graphics}
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{graphics, psfrag}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{enumitem} 
\usepackage{url}
\usepackage{array,dcolumn,booktabs}
\usepackage{pdflscape}
\usepackage{amsthm}
\usepackage{ulem}
\usepackage{listings}

\newcounter{task}
\newcommand{\task}{\stepcounter{task}\paragraph{Task \thetask~--~Solution\\}}

\usepackage{pifont}

\newcommand{\header}{
  \begin{center}
  \fbox{\parbox{11cm}{
    \begin{center}
      {\Large 6. Problem Session -- Solution\\ \vspace{0.2em}
        {\bf Secure Channels}\\ \vspace{0.7em} (Winter Term 2014/2015)\\
        \vspace{0.2em} \firstnameone \lastnameone\\
        \vspace{0.2em} \matriculationnumberone\\
        \vspace{0.2em} \firstnametwo \lastnametwo\\
        \vspace{0.2em} \matriculationnumbertwo \\
       \vspace{0.2em} \firstnamethree \lastnamethree\\
        \vspace{0.2em} \matriculationnumberthree
    }
    \end{center}
  }}
  \end{center}
}


%-------------------------------------------------------------------------------
%---------------------------- EDIT FROM HERE -----------------------------------
%-------------------------------------------------------------------------------

\newcommand{\firstnameone}{Jiaqi	}
\newcommand{\lastnameone}{Weng}
\newcommand{\matriculationnumberone}{115131}

\newcommand{\firstnametwo}{Vasilii	}
\newcommand{\lastnametwo}{Ponteleev}
\newcommand{\matriculationnumbertwo}{115151}

\newcommand{\firstnamethree}{Naveeni	}
\newcommand{\lastnamethree}{ Kumar Goswam}
\newcommand{\matriculationnumberthree}{113967}

\begin{document}
\pagestyle{plain}
\header


% number of tasks are automatically generated
\task
a)\\
IND-CPA means distinguish between real or random, only plain text queries are allowed.\\
$x_0$ = N \\
$x_i$ = $E_k$ ($m_i$ $\oplus$ $x_{i - 1}$), $C_i$ = $x_i \oplus S_i$\\
Since N = const, $S_0$ ... $S_l$ also stays const on each query\\\\
$q_1$ = (N, $M_1$, $M_2$) $\rightarrow$ (($C_1$, $C_2$), $T$)\\
$q_2$ = (N, $M_1$, $M_3$) $\rightarrow$ (($C_{1}^{'}$, $C_3$), $T^{'}$)\\
if $C_1$ = $C_{1}^{'}$ then real, else random\\
b)\\


\task
Follow the Ind-CPA scenario.\\
q1: send LR(b, m0(0,H), m1(0,H)), b is random value of \{0, 1\}\\
O1: get $T=Mac(0,H)$, $C=E_k(0,T)$\\
q2: send LR(b, m0(0,H), m1(1,H)), b is random value of \{0, 1\}\\
if response of T'=T and C'=C, we guess b=0, else b=1.\\
because the MAC is uf-cma secure, T' = T with only negligible probability. \\
so the uf-cma secure Mac could lead ind-CPA insecure, so it is insufficient.

\task
Prove HCBC1 is not RoR-OPRP-CCA secure.\\
we send Ciphertext C to HCBC1 Decryption oracle 1 by 1 byte.\\
q1: send $(C,C)$ to oracle,\\
O1: response $M_1=D_k(C) \oplus H_l(C)$\\
q forge: send the 3rd byte also $C$ to oracle, guess the $M_2=M_1$\\
O2: response $M_2=D_k(C) \oplus H_l(C)=M_1$\\
so we can get the HCBC1 is not RoR-OPRP-CCA secure.

\task
a)\\
set parameters:\\
frame width is w\\
Nonce length is l\\
tag length is r\\
ctr  $(N || 0....0)$, length is n\\
const0 and const1, length is n\\
\\
Key Stream Generation of CENC\\
CENCKSGen: input ctr, l, output S\\
\begin{lstlisting}[frame=single]
for j from 0 to (l/w)-1
  L=Ek(ctr) 
  ctr=inc(ctr)
  for i from 0 to w-1
      S(wj+i)=Ek(ctr) xor L
      ctr=inc(ctr)
      if wj+i = l-1
        return S(S_0 || S_1....|| S_l)
\end{lstlisting}
Encryption:input const0, const1, M, N, H, output C,T
\begin{lstlisting}[frame=single]
S0=Ek(const0)
S1=Ek(const1)
l=|M|/n
ctr  = (N || 0....0) n bit
S=CENCKSGen(ctr, l+1)
S2=first(n,S)
S3=last(nl,S)
C=M xor first(|M|, S3)
Hash0=Hash(S0, C)
Hash1=Hash(S1, H)
T = Hash0 xor Hash1 xor S2
T = first(r, T)
return (T,C)
\end{lstlisting}
Decryption: input const0, const1, C, T, N, H, output M
\begin{lstlisting}[frame=single]
S0=Ek(const0)
S1=Ek(const1)
l=|C|/n
ctr  = (N || 0....0) n bit
S=CENCKSGen(ctr, l+1)
S2=first(n,S)
Hash0=Hash(S0, C)
Hash1=Hash(S1, H)
T' = Hash0 xor Hash1 xor S2
T' = first(r, T')
if T' != T then return rejection
S3=last(nl,S)
M=C xor first(|C|, S3)
return M
\end{lstlisting}
Hash:
input S,M, output HashC
\begin{lstlisting}[frame=single]
M=Pad(M)
l = |M| / n
Hash = 0...0(n bit)
for i from 0 to l-1
    Hash = (Hash xor M(i)) * S
return Hash
\end{lstlisting}
b)\\
because of small amount of memory, we have no space for saving much data.\\
So we need use memory as least as possible, my solution is calculate the S when Decryption 1 by 1 byte\\
Decryption: input const0, const1, C, T,  N, H, output M
\begin{lstlisting}[frame=single]
S=Ek(const0)
S'=Hash(S, C)
l=|C|/n
ctr  = (N || 0....0) n bit
L=Ek(ctr) 
ctr=inc(ctr)
T' = S' xor Ek(ctr) xor L
S=Ek(const1)
S'=Hash(S,H)
T' = T' xor S'
T' = first(r, T')
if T' != T then return rejection

for i from 0 to w-2
      S=Ek(ctr) xor L
      M(i)=C(i) xor S
      ctr=inc(ctr)

for j from 1 to (l/w)-1
  L=Ek(ctr) 
  ctr=inc(ctr)
  for i from 0 to w-1
      S = Ek(ctr) xor L
      ctr=inc(ctr)
      M(wj+i) = C(wj+i) xor S
      if wj+i == |C|/n
          return M
\end{lstlisting}
c)\\
nonce misusing.\\
q1: (M,N,H) get (T, C)\\ 
q2: (M,N,H') get (T', C)\\
q3: (M',N',H) get (T'', C')\\
forge: $(T \oplus T' \oplus T'' , C')$ will get (M', N', H')\\ 
d)\\
do not use the nonce, and make the header consist of nonce and associated data.\\
e)\\
SIV cannot save much memory using in this case, because T of SIV is calculate by M and H,\\
so it should decryption all M first, and then verification, there must be memory to save the data M.\\
SIV is secure even if nonce misusing.

\end{document}
